import java.util.Arrays;

public class 数组经典练习 {
    public static void main(String[] args) {
        //查找数组中的指定元素(顺序查找)
        //给定一个数组, 再给定一个元素, 找出该元素在数组中的位置
        //int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        //System.out.println(find(arr,5));


        //查找数组中的指定元素(二分查找)
        //二分查找的思路是先取中间位置的元素, 然后使用待查找元素与数组中间元素进行比较：
        //int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        //System.out.println(binarySearch(arr,6));


        //数组排序(冒泡排序)
        //给定一个数组,让数组升序(降序)的格式来排序
        //思路:假设排升序：
        //1. 将数组中相邻元素从前往后依次进行比较，如果前一个元素比后一个元素大，则交换，一趟下来后最大元素
        //就在数组的末尾
        //2. 依次从上上述过程，直到数组中所有的元素都排列好
        int[] arr = {9,5,2,7,6,8,11,28,65};
        bubbleSort(arr);  //冒泡排序
        //Arrays.sort(arr);   //冒泡排序性能较低,java中内置了更高效的排序算法
        System.out.println(Arrays.toString(arr));

    }
    public static void bubbleSort(int[] arr){
        for(int i=0;i<arr.length;i++){   //确定需要冒泡多少趟
            for(int j=0;j<arr.length-i-1;j++){   //进行每一趟冒泡过程 . length-i-1 是因为每一趟冒泡后，最大的元素就在数组的末尾，不需要再比较了,因此可以逐渐缩小范围
                if(arr[j]>arr[j+1]){   //因为数组是升序排序，因此若前一个元素比后一个元素大，则交换,
                                      //若是降序排序，则改为 arr[j-1]<arr[j]
                    //交换元素
                    int tmp = arr[j];  //定义一个临时变量，用于交换元素
                    arr[j]=arr[j+1];   //将arr[j+1]的值(小的)赋给arr[j]
                    arr[j+1]= tmp;    //将tmp的值(大的)赋给arr[j+1]
                }
            }
        }
    }
public static int binarySearch(int[] arr,int toFind){
        //[left,right]
        int left =0;  //数组下标为0的元素开始
        int right =arr.length-1;   //数组最右侧元素
        while(left<=right){   //当最左侧元素小于等于最右侧元素时
            int mid = (left+right)/2;
            if(toFind<arr[mid]) {   //去左侧区间找
                right = mid - 1;  //更新右侧边界:范围由mid向前移一位
            }else if(toFind>arr[mid]) {   //去右侧区间找
                left = mid + 1;   //更新左侧边界:范围由mid向后移一位
            }else{
                return mid;   //说明找到了
            }
        }
      return -1;    //循环结束,说明没找到
}
    public static int find(int[] arr,int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1;
    }
}
